package com.zjsru.leetcode75.level1;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author: cookLee
 * @Date: 2024-01-02
 * 迷宫中离入口最近的出口
 * 给你一个 m x n 的迷宫矩阵 maze （下标从 0 开始），矩阵中有空格子（用 '.' 表示）和墙（用 '+' 表示）。同时给你迷宫的入口 entrance ，用 entrance = [entrancerow, entrancecol] 表示你一开始所在格子的行和列。
 */
public class NearestExit {

    /**
     * 主
     * \
     * 输入：maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]], entrance = [1,2]
     * 输出：1
     * 解释：总共有 3 个出口，分别位于 (1,0)，(0,2) 和 (2,3) 。
     * 一开始，你在入口格子 (1,2) 处。
     * - 你可以往左移动 2 步到达 (1,0) 。
     * - 你可以往上移动 1 步到达 (0,2) 。
     * 从入口处没法到达 (2,3) 。
     * 所以，最近的出口是 (0,2) ，距离为 1 步。
     * \
     * 输入：maze = [["+","+","+"],[".",".","."],["+","+","+"]], entrance = [1,0]
     * 输出：2
     * 解释：迷宫中只有 1 个出口，在 (1,2) 处。
     * (1,0) 不算出口，因为它是入口格子。
     * 初始时，你在入口与格子 (1,0) 处。
     * - 你可以往右移动 2 步到达 (1,2) 处。
     * 所以，最近的出口为 (1,2) ，距离为 2 步。
     * \
     * @param args args
     */
    public static void main(String[] args) {
        NearestExit nearestExit = new NearestExit();
        char[][] maze = new char[][]{{'+','+','.','+'},{'.','.','.','+'},{'+','+','+','.'}};
        int[] entrance = new int[]{1,2} ;
        System.out.println(nearestExit.nearestExit(maze, entrance));
    }

    /**
     * 最近出口
     * bfs
     * @param maze     迷宫
     * @param entrance 入口
     * @return int
     */
    public int nearestExit(char[][] maze, int[] entrance) {
        int m = maze.length;
        int n = maze[0].length;
        //方向变量
        int[][] directions = {{0, 1, 0, -1}, {1, 0, -1, 0}};

        //记录已经访问过的点的坐标
        Queue<int[]> queue = new LinkedList<>();
        //将入口加入队列，最后一位表示当前走了几步
        queue.offer(new int[]{entrance[0], entrance[1], 0});
        // 遍历到的坐标变为墙 防止重复遍历
        maze[entrance[0]][entrance[1]] = '+';

        while (!queue.isEmpty()) {
            int[] currentLocal = queue.poll();
            //行坐标
            int row = currentLocal[0];
            //列坐标
            int col = currentLocal[1];
            //轮流尝试四个方向
            for (int i = 0; i < 4; i++) {
                int x = row + directions[0][i];
                int y = col + directions[1][i];
                // 新坐标合法 且 不为墙
                if (x >= 0 && x <= m - 1 && y >= 0 && y <= n - 1 && maze[x][y] == '.') {
                    if (x == 0 || x == m - 1 || y == 0 || y == n - 1) {
                        //currentLocal[2]是int数组的最后一位，存储了从入口到当前位置的步数,同时 多迈一步才能走出迷宫
                        return currentLocal[2] + 1;
                    }
                    queue.offer(new int[]{x, y, currentLocal[2] + 1});
                    maze[x][y] = '+';
                }
            }
        }
        return -1;
    }

}
